#include "heap.h"

Heap::Heap(int max)
{
        heap = (int *)calloc(max, sizeof(int)); //Le doy un tamaño al heap
        heap[0] = 0;
}

void Heap:: Decrease_Key(int index, int new_key){
    if(index <= heap[0] && new_key < heap[index]){
        heap[index] = new_key;
        Float(index);
    }
}

void Heap:: Float(int index){
    if(index>0){
        int aux, new_index=index/2;
        if(new_index > 0 && heap[new_index] > heap[index]){
            aux = heap[index];
            heap[index] = heap[new_index];
            heap[new_index] = aux;
            Float(new_index);
        }
    }
}

int* Heap:: Build_Heap(int* array){
    heap_aux = array;
    if(array[0] > 0){
        for(int i=array[0]/2; i>0; i--){
            Heapify_aux(i);
        }
    }
    return heap_aux;
}

void Heap:: Impr(bool all)
{
    int start=1;

    if (all)
        start= 0;

    for(int i= start; i<=heap[0]; i++)
    {
        cout << heap[i] << " | ";
    }
    cout << endl;
    //cout << "------------------------------" << endl;
}

void Heap:: Insert(int num){
    heap[0]++;
    heap[heap[0]] = num;
    Float(heap[0]);
}

void Heap:: Delete(int index){
    if(heap[0] > 0 && index <= heap[0]){
        int aux = heap[heap[0]];
        heap[heap[0]] = heap[index];
        heap[index] = aux;
        heap[0]--;
        Heapify(index);
    }
}

void Heap:: Heapify(int index){
    if(index < heap[0]){
        int aux, new_index=index*2, new_index2=index*2+1;
        if(new_index <= heap[0] && new_index2 <= heap[0]){
            if(heap[new_index] < heap[new_index2]){
                aux = heap[new_index];
                heap[new_index] = heap[index];
                heap[index] = aux;
                Heapify(new_index);
            }else{
                aux = heap[new_index2];
                heap[new_index2] = heap[index];
                heap[index] = aux;
                Heapify(new_index2);
            }
        }else{
            if(new_index <= heap[0]){
                aux = heap[new_index];
                heap[new_index] = heap[index];
                heap[index] = aux;
                Heapify(new_index);
            }
            if(new_index2 <= heap[0]){
                aux = heap[new_index2];
                heap[new_index2] = heap[index];
                heap[index] = aux;
                Heapify(new_index2);
            }
        }
    }
}

void Heap:: Heapify_aux(int index){
    if(index < heap_aux[0]){
        int aux, new_index=index*2, new_index2=index*2+1;
        if(new_index <= heap_aux[0] && new_index2 <= heap_aux[0]){
            if(heap_aux[new_index] < heap_aux[new_index2]){
                aux = heap_aux[new_index];
                heap_aux[new_index] = heap_aux[index];
                heap_aux[index] = aux;
                Heapify_aux(new_index);
            }else{
                aux = heap_aux[new_index2];
                heap_aux[new_index2] = heap_aux[index];
                heap_aux[index] = aux;
                Heapify_aux(new_index2);
            }
        }else{
            if(new_index <= heap_aux[0]){
                aux = heap_aux[new_index];
                heap_aux[new_index] = heap_aux[index];
                heap_aux[index] = aux;
                Heapify_aux(new_index);
            }
            if(new_index2 <= heap_aux[0]){
                aux = heap_aux[new_index2];
                heap_aux[new_index2] = heap_aux[index];
                heap_aux[index] = aux;
                Heapify_aux(new_index2);
            }
        }
    }
}

